Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Additive coloring (2)
- Combinatorial Nullstellensatz (2)
- Discharging method (2)
- Dynamic coloring (2)
- Lucky labeling (2)
-
- Reducible configuration (2)
- Cartesian product of graphs (1)
- Coloring (1)
- Coloring of graphs and hypergraphs (1)
- Combinatorics (1)
- Computational proof (1)
- Degree sequence (1)
- Discharging (1)
- Discrete tomography (1)
- Distinguishing (1)
- List distinguishing (1)
- Packing (1)
- Planar graph (1)
- Planar graphs (1)
- Sparse Graphs (1)
- Square (1)
- Strong Chromatic Index (1)
- Strong Edge Coloring (1)
- Strongly regular graphs (1)
- Subcubic (1)
Articles 1 - 12 of 12
Full-Text Articles in Physical Sciences and Mathematics
The Knill Graph Dimension From The Minimum Clique Cover, Kassahun Betre, Evatt Salinger
The Knill Graph Dimension From The Minimum Clique Cover, Kassahun Betre, Evatt Salinger
Faculty Publications
In this paper we prove that the recursive (Knill) dimension of the join of two graphs has a simple formula in terms of the dimensions of the component graphs: dim(G1+G2)=1+dimG1+dimG2. We use this formula to derive an expression for the Knill dimension of a graph from its minimum clique cover. A corollary of the formula is that a graph made of the arbitrary union of complete graphs KN of the same order N will have dimension N−1. We finish by finding lower and upper bounds on the Knill dimension of a graph in terms of its clique number.
On The Strong Chromatic Index Of Sparse Graphs, Philip Deorsey, Jennifer Diemunsch, Michael Ferrara, Nathan Graber, Stephen Hartke, Sogol Jahanbekam, Bernard Lidicky, Luke Nelsen, Derrick Stolee, Eric Sullivan
On The Strong Chromatic Index Of Sparse Graphs, Philip Deorsey, Jennifer Diemunsch, Michael Ferrara, Nathan Graber, Stephen Hartke, Sogol Jahanbekam, Bernard Lidicky, Luke Nelsen, Derrick Stolee, Eric Sullivan
Faculty Publications
The strong chromatic index of a graph G, denoted χ′s(G), is the least number of colors needed to edge-color G so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted χ′s,ℓ(G), is the least integer k such that if arbitrary lists of size k are assigned to each edge then G can be edge-colored from those lists where edges at distance at most two receive distinct colors.We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if G is a subcubic planar graph with girth(G)≥41 then χ′s,ℓ(G)≤5, answering a question …
Additive List Coloring Of Planar Graphs With Given Girth, Axel Brandt, Sogol Jahanbekam, Jennifer Diemunsch
Additive List Coloring Of Planar Graphs With Given Girth, Axel Brandt, Sogol Jahanbekam, Jennifer Diemunsch
Faculty Publications
An additive coloring of a graph G is a labeling of the vertices of G from {1,2,...,k} such that two adjacent vertices have distinct sums of labels on their neighbors. The least integer k for which a graph G has an additive coloring is called the additive coloring number of G, denoted \luck(G). Additive coloring is also studied under the names lucky labeling and open distinguishing. In this paper, we improve the current bounds on the additive coloring number for particular classes of graphs by proving results for a list version of additive coloring. We apply the discharging method and …
Weak Dynamic Coloring Of Planar Graphs, Caroline Accurso, Vitaliy Chernyshov, Leaha Hand, Sogol Jahanbekam, Paul Wenger
Weak Dynamic Coloring Of Planar Graphs, Caroline Accurso, Vitaliy Chernyshov, Leaha Hand, Sogol Jahanbekam, Paul Wenger
Faculty Publications
The k-weak-dynamic number of a graph G is the smallest number of colors we need to color the vertices of G in such a way that each vertex v of degree d(v) sees at least min{k, d(v)} colors on its neighborhood. We use reducible configurations and list coloring of graphs to prove that all planar graphs have 3-weak-dynamic number at most 6.
List-Distinguishing Cartesian Products Of Cliques, Michael Ferrara, Zoltan Füredi, Sogol Jahanbekam, Paul Wenger
List-Distinguishing Cartesian Products Of Cliques, Michael Ferrara, Zoltan Füredi, Sogol Jahanbekam, Paul Wenger
Faculty Publications
The distinguishing number of a graph G, denoted D(G), is the minimum number of colors needed to produce a coloring of the vertices of G so that every nontrivial isomorphism interchanges vertices of different colors. A list assignment L on a graph G is a function that assigns each vertex of G a set of colors. An L-coloring of G is a coloring in which each vertex is colored with a color from L(v). The list distinguishing number of G, denoted Dℓ(G) is the minimum k such that every list assignment L that assigns a list of size at least …
The Chromatic Number Of The Square Of Subcubic Planar Graphs, Stephen Hartke, Sogol Jahanbekam, Brent Thomas
The Chromatic Number Of The Square Of Subcubic Planar Graphs, Stephen Hartke, Sogol Jahanbekam, Brent Thomas
Faculty Publications
Wegner conjectured in 1977 that the square of every planar graph with maximum degree at most 3 is 7-colorable. We prove this conjecture using the discharging method and computational techniques to verify reducible configurations.
Extremal Theorems For Degree Sequence Packing And The Two-Color Discrete Tomography Problem, Jennifer Diemunsch, Michael Ferrara, Sogol Jahanbekam, James Shook
Extremal Theorems For Degree Sequence Packing And The Two-Color Discrete Tomography Problem, Jennifer Diemunsch, Michael Ferrara, Sogol Jahanbekam, James Shook
Faculty Publications
No abstract provided.
Lucky Choice Number Of Planar Graphs With Given Girth, Axel Brandt, Jennifer Diemunsch, Sogol Jahanbekam
Lucky Choice Number Of Planar Graphs With Given Girth, Axel Brandt, Jennifer Diemunsch, Sogol Jahanbekam
Faculty Publications
No abstract provided.
Antimagic-Type Labelings, Sogol Jahanbekam
On The Dynamic Coloring Of Cartesian Product Graphs., Saieed Akbari, Maryam Ghanbari, S. Jahanbekam
On The Dynamic Coloring Of Cartesian Product Graphs., Saieed Akbari, Maryam Ghanbari, S. Jahanbekam
Faculty Publications
No abstract provided.
On The Dynamic Coloring Of Strongly Regular Graphs, Saieed Akbari, Maryam Ghanbari, Sogol Jahanbekam
On The Dynamic Coloring Of Strongly Regular Graphs, Saieed Akbari, Maryam Ghanbari, Sogol Jahanbekam
Faculty Publications
No abstract provided.
The 1, 2-Conjecture For Graphs With Relatively Small Chromatic Number, Sogol Jahanbekam, Douglas West
The 1, 2-Conjecture For Graphs With Relatively Small Chromatic Number, Sogol Jahanbekam, Douglas West
Faculty Publications
No abstract provided.