Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Institution
- Keyword
-
- Competitive coloring (4)
- Relaxed coloring (3)
- Additive coloring (2)
- Combinatorial Nullstellensatz (2)
- Combinatorics (2)
-
- Discharging method (2)
- Dynamic coloring (2)
- Graph pebbling (2)
- Lemke graph (2)
- Lucky labeling (2)
- Reducible configuration (2)
- 05B15 (1)
- 11T22 (1)
- 52B15 (1)
- Algorithms (1)
- Cartesian product of graphs (1)
- Clique (1)
- Coloring (1)
- Coloring of graphs and hypergraphs (1)
- Computational proof (1)
- Cyclotomy (1)
- Degree sequence (1)
- Delannoy number (1)
- Discharging (1)
- Discrete tomography (1)
- Distinguishing (1)
- Edge coloring (1)
- Facet (1)
- Forest (1)
- Game chromatic number (1)
Articles 1 - 24 of 24
Full-Text Articles in Discrete Mathematics and Combinatorics
A Bit-Parallel Tabu Search Algorithm For Finding Es2 -Optimal And Minimax-Optimal Supersaturated Designs, Luis B. Morales, Dursun A. Bulutoglu
A Bit-Parallel Tabu Search Algorithm For Finding Es2 -Optimal And Minimax-Optimal Supersaturated Designs, Luis B. Morales, Dursun A. Bulutoglu
Faculty Publications
We prove the equivalence of two-symbol supersaturated designs (SSDs) with N (even) rows, m columns, smax=4t+i, where i ∈ {0,2}, t ∈ Z≥0 and resolvable incomplete block designs (RIBDs) whose any two blocks intersect in at most (N+4t+i)/4 points. Using this equivalence, we formulate the search for two-symbol E(s2)-optimal and minimax-optimal SSDs with smax ∈ {2,4,6} as a search for RIBDs whose blocks intersect accordingly. This allows developing a bit-parallel tabu search (TS) algorithm. The TS algorithm found E(s2)-optimal and minimax-optimal SSDs achieving the sharpest known E(s2) lower bound with …
Legendre G-Array Pairs And The Theoretical Unification Of Several G-Array Families, K. T. Arasu, Dursun A. Bulutoglu, J. R. Hollon
Legendre G-Array Pairs And The Theoretical Unification Of Several G-Array Families, K. T. Arasu, Dursun A. Bulutoglu, J. R. Hollon
Faculty Publications
We investigate how Legendre G-array pairs are related to several different perfect binary G-array families. In particular we study the relations between Legendre G-array pairs, Sidelnikov-Lempel-Cohn-Eastman ℤq−1-arrays, Yamada-Pott G-array pairs, Ding-Helleseth-Martinsen ℤ2×ℤmp-arrays, Yamada ℤ(q−1)/2-arrays, Szekeres ℤmp-array pairs, Paley ℤmp-array pairs, and Baumert ℤm1p1×ℤm2p2-array pairs. Our work also solves one of the two open problems posed in Ding~[J. Combin. Des. 16 (2008), 164-171]. Moreover, we provide several computer search based existence and non-existence results regarding Legendre ℤn-array pairs. …
Graph Pebbling Algorithms And Lemke Graphs, Charles A. Cusack, Aaron Green, Airat Bekmetjev, Mark Powers
Graph Pebbling Algorithms And Lemke Graphs, Charles A. Cusack, Aaron Green, Airat Bekmetjev, Mark Powers
Faculty Publications
Given a simple, connected graph, a pebbling configuration (or just configuration) is a function from its vertex set to the nonnegative integers. A pebbling move between adjacent vertices removes two pebbles from one vertex and adds one pebble to the other. A vertex r is said to be reachable from a configuration if there exists a sequence of pebbling moves that places at least one pebble on r. A configuration is solvable if every vertex is reachable. The pebbling number π(G) of a graph G is the minimum integer such that every configuration of size π(G) on G …
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.
Two-Pebbling And Odd-Two-Pebbling Are Not Equivalent, Charles A. Cusack, Airat Bekmetjev, Mark Powers
Two-Pebbling And Odd-Two-Pebbling Are Not Equivalent, Charles A. Cusack, Airat Bekmetjev, Mark Powers
Faculty Publications
Let G be a connected graph. A configuration of pebbles assigns a nonnegative integer number of pebbles to each vertex of G. A move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if any vertex can get at least one pebble through a sequence of moves. The pebbling number of G, denoted π(G), is the smallest integer such that any configuration of π(G) pebbles on G is solvable. A graph has the two-pebbling property if after placing more than 2π(G) -- q pebbles on G …
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.
The Relaxed Edge-Coloring Game And K-Degenerate Graphs, Charles Dunn, David Morawski, Jennifer Firkins Nordstrom
The Relaxed Edge-Coloring Game And K-Degenerate Graphs, Charles Dunn, David Morawski, Jennifer Firkins Nordstrom
Faculty Publications
The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with ∆(F) = ∆, then the first player, Alice, has a winning strategy for this game with r = ∆ − j and d ≥ 2j + 2 for 0 ≤ j ≤ ∆ − 1. This both improves and generalizes the result for trees in [10]. More broadly, we generalize the main result in [10] …
The Game Chromatic Number Of Trees And Forests, Charles Dunn, Victor Larsen, Troy Retter, Kira Lindke, Dustin Toci
The Game Chromatic Number Of Trees And Forests, Charles Dunn, Victor Larsen, Troy Retter, Kira Lindke, Dustin Toci
Faculty Publications
While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining in polynomial time the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree …
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.
The Lp Relaxation Orthogonal Array Polytope And Its Permutation Symmetries, Andrew J. Geyer, Dursun A. Bulutoglu, Steven J. Rosenberg
The Lp Relaxation Orthogonal Array Polytope And Its Permutation Symmetries, Andrew J. Geyer, Dursun A. Bulutoglu, Steven J. Rosenberg
Faculty Publications
Symmetry plays a fundamental role in design of experiments. In particular, symmetries of factorial designs that preserve their statistical properties are exploited to find designs with the best statistical properties. By using a result proved by Rosenberg [6], the concept of the LP relaxation orthogonal array polytope is developed and studied. A complete characterization of the permutation symmetry group of this polytope is made. Also, this characterization is verified computationally for many cases. Finally, a proof is provided.
Antimagic-Type Labelings, Sogol Jahanbekam
A Note On Independent Sets In Graphs With Large Minimum Degree And Small Cliques, Jeremy Lyle
A Note On Independent Sets In Graphs With Large Minimum Degree And Small Cliques, Jeremy Lyle
Faculty Publications
Graphs with large minimum degree containing no copy of a clique on r vertices (Kr) must contain relatively large independent sets. A classical result of Andrásfai, Erdös, and Sós implies that Kr-free graphs G with degree larger than ((3r − 7)/(3r − 4))|V(G)| must be (r − 1)-partite. An obvious consequence of this result is that the same degree threshold implies an independent set of order (1/(r − 1))|V(G)|. The following paper provides improved bounds on the minimum degree which would imply the …
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.
Complete Multipartite Graphs And The Relaxed Coloring Game, Charles Dunn
Complete Multipartite Graphs And The Relaxed Coloring Game, Charles Dunn
Faculty Publications
Let k be a positive integer, d be a nonnegative integer, and G be a finite graph. Two players, Alice and Bob, play a game on G by coloring the uncolored vertices with colors from a set X of k colors. At all times, the subgraph induced by a color class must have maximum degree at most d. Alice wins the game if all vertices are eventually colored; otherwise, Bob wins. The least k such that Alice has a winning strategy is called the d-relaxed game chromatic number of G, denoted χ gd (G). …
Higher Dimensional Lattice Chains And Delannoy Numbers, John S. Caughman, Charles L. Dunn, Nancy Ann Neudauer, Colin L. Starr
Higher Dimensional Lattice Chains And Delannoy Numbers, John S. Caughman, Charles L. Dunn, Nancy Ann Neudauer, Colin L. Starr
Faculty Publications
Fix nonnegative integers n1 , . . ., nd, and let L denote the lattice of points (a1 , . . ., ad) ∈ ℤd that satisfy 0 ≤ ai ≤ ni for 1 ≤ i ≤ d. Let L be partially ordered by the usual dominance ordering. In this paper we use elementary combinatorial arguments to derive new expressions for the number of chains and the number of Delannoy paths in L. Setting ni = n (for all i) in these expressions yields a new …
Clique-Relaxed Graph Coloring, Charles Dunn, Jennifer Firkins Nordstrom, Cassandra Naymie, Erin Pitney, William Sehorn, Charlie Suer
Clique-Relaxed Graph Coloring, Charles Dunn, Jennifer Firkins Nordstrom, Cassandra Naymie, Erin Pitney, William Sehorn, Charlie Suer
Faculty Publications
We define a generalization of the chromatic number of a graph G called the k-clique-relaxed chromatic number, denoted χ(k)(G). We prove bounds on χ(k)(G) for all graphs G, including corollaries for outerplanar and planar graphs. We also define the k-clique-relaxed game chromatic number, χg(k)(G), of a graph G. We prove χg(2)(G)≤ 4 for all outerplanar graphs G, and give an example of an outerplanar graph H with χg(2)(H) ≥ 3. Finally, we prove that if H is a member …
The Relaxed Game Chromatic Index Of K-Degenerate Graphs, Charles Dunn
The Relaxed Game Chromatic Index Of K-Degenerate Graphs, Charles Dunn
Faculty Publications
The (r, d)-relaxed coloring game is a two-player game played on the vertex set of a graph G. We consider a natural analogue to this game on the edge set of G called the (r, d)-relaxed edge-coloring game. We consider this game on trees and more generally, on k-degenerate graphs. We show that if G is k-degenerate with ∆(G) = ∆, then the first player, Alice, has a winning strategy for this game with r = ∆+k−1 and d≥2k2 + 4k.