Distance graphs with maximum chromatic number

Distance graphs with maximum chromatic number

Let $D$ be a finite set of integers. The distance graph $G(D)$ has the set of integers as vertices and two vertices at distance $d ∈D$ are adjacent in $G(D)$. A conjecture of Xuding Zhu states that if the chromatic number of $G (D)$ achieves its maximum value $|D|+1$ then the graph has a clique of o...

Bibliografski detalji
Glavni autori:	Javier Barajas, Oriol Serra
Format:	Članak
Jezik:	English
Izdano:	Discrete Mathematics & Theoretical Computer Science 2005-01-01
Serija:	Discrete Mathematics & Theoretical Computer Science
Teme:	distance graphs chromatic number [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co]
Online pristup:	https://dmtcs.episciences.org/3391/pdf

Slični predmeti

An upper bound for the chromatic number of line graphs
od: Andrew D. King, i dr.
Izdano: (2005-01-01)

(k − 2)-linear connected components in hypergraphs of rank k
od: Florian Galliot, i dr.
Izdano: (2023-11-01)

On Kerov polynomials for Jack characters (extended abstract)
od: Valentin Féray, i dr.
Izdano: (2013-01-01)

Staircase Macdonald polynomials and the $q$-Discriminant
od: Adrien Boussicault, i dr.
Izdano: (2008-01-01)

On the Minimum Number of Completely 3-Scrambling Permutations
od: Jun Tarui
Izdano: (2005-01-01)

Indecomposable permutations with a given number of cycles
od: Robert Cori, i dr.
Izdano: (2009-01-01)

On the $L(p,1)$-labelling of graphs
od: Daniel Gonçalves
Izdano: (2005-01-01)

A product formula for the TASEP on a ring
od: Erik Aas, i dr.
Izdano: (2014-01-01)

Noncommutative Symmetric Hall-Littlewood Polynomials
od: Lenny Tevlin
Izdano: (2011-01-01)

Combinatorics of k-shapes and Genocchi numbers
od: Florent Hivert, i dr.
Izdano: (2011-01-01)

Chromatic Turán problems and a new upper bound for the Turán density of $\mathcal{K}_4^-$
od: John Talbot
Izdano: (2005-01-01)

Noncommutative symmetric functions III : Deformations of Cauchy and convolution algebras
od: Gérard Duchamp, i dr.
Izdano: (1997-01-01)

Packing non-returning A-paths algorithmically
od: Gyula Pap
Izdano: (2005-01-01)

Multigraph decomposition into multigraphs with two underlying edges
od: Miri Priesler, i dr.
Izdano: (2005-01-01)

Hamiltonian Chains in Hypergraphs
od: Gyula Y. Katona
Izdano: (2005-01-01)

Counting Polyominoes on Twisted Cylinders
od: Gill Barequet, i dr.
Izdano: (2005-01-01)

Counting Shi regions with a fixed separating wall
od: Susanna Fishel, i dr.
Izdano: (2011-01-01)

A Quantization of a theorem of Goulden and Jackson
od: Matjaž Konvalinka, i dr.
Izdano: (2008-01-01)

Enumeration of alternating sign matrices of even size (quasi)-invariant under a quarter-turn rotation
od: Jean-Christophe Aval, i dr.
Izdano: (2009-01-01)

$K_{\ell}^{-}$-factors in graphs
od: Daniela Kühn, i dr.
Izdano: (2005-01-01)

Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs
od: Alexandre Bazin, i dr.
Izdano: (2023-04-01)

Acyclic Coloring of Graphs of Maximum Degree $\Delta$
od: Guillaume Fertin, i dr.
Izdano: (2005-01-01)

A sufficient condition for bicolorable hypergraphs
od: David Défossez
Izdano: (2005-01-01)

Excluded subposets in the Boolean lattice
od: Gyula O.H. Katona
Izdano: (2005-01-01)

A Min-Max theorem about the Road Coloring Conjecture
od: Rajneesh Hegde, i dr.
Izdano: (2005-01-01)

Discrepancy of Products of Hypergraphs
od: Benjamin Doerr, i dr.
Izdano: (2005-01-01)

Structure of spaces of rhombus tilings in the lexicograhic case
od: Éric Rémila
Izdano: (2005-01-01)

Mader Tools
od: Frank Göring
Izdano: (2005-01-01)

Fast separation in a graph with an excluded minor
od: Bruce Reed, i dr.
Izdano: (2005-01-01)

Affine permutations and rational slope parking functions
od: Eugene Gorsky, i dr.
Izdano: (2014-01-01)

A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants (condensed version)
od: J. Haglund
Izdano: (2011-01-01)

On the enumeration of column-convex permutominoes
od: Nicholas R. Beaton, i dr.
Izdano: (2011-01-01)

The purity of set-systems related to Grassmann necklaces
od: Vladimir Danilov, i dr.
Izdano: (2014-01-01)

Combinatorial properties of permutation tableaux
od: Alexander Burstein, i dr.
Izdano: (2008-01-01)

A bijective proof of a factorization formula for Macdonald polynomials at roots of unity
od: F. Descouens, i dr.
Izdano: (2008-01-01)

A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests
od: Heesung Shin, i dr.
Izdano: (2009-01-01)

A bijection between shrubs and series-parallel posets
od: Frédéric Chapoton
Izdano: (2008-01-01)

Statistics on staircase tableaux, eulerian and mahonian statistics
od: Sylvie Corteel, i dr.
Izdano: (2011-01-01)

The quasiinvariants of the symmetric group
od: Jason Bandlow, i dr.
Izdano: (2008-01-01)

Combinatorial interpretation and positivity of Kerov's character polynomials
od: Valentin Féray
Izdano: (2008-01-01)