Graph coloring with cardinality constraints on the neighborhoods

DOI10.1016/j.disopt.2009.04.005zbMath1175.05053OpenAlexW2000281366MaRDI QIDQ1040081

Christophe Picouleau, Marie-Christine Costa, Dominique de Werra, Bernard Ries

Publication date: 23 November 2009

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: http://doc.rero.ch/record/324621/files/neighborhood.pdf

zbMATH Keywords

treebipartite graphvertex coloringcardinality constrained colorings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Reconstructing binary matrices with timetabling constraints ⋮ Group path covering and distance two labeling of graphs ⋮ Algorithms for a shared resource scheduling problem in which some level of conflict is tolerable ⋮ Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions ⋮ On the use of graphs in discrete tomography

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded vertex colorings of graphs
• Local coloring of Kneser graphs
• A distance-labelling problem for hypercubes
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Colouring a graph frugally
• Total colouring regular bipartite graphs is NP-hard
• Equitable coloring of trees
• Mutual exclusion scheduling
• Feasible edge colorings of trees with cardinality constraints
• \((p,1)\)-total labelling of graphs
• A survey on the distance-colouring of graphs
• General neighbour-distinguishing index of a graph
• Semi-total graph colourings, the beta parameter, and total chromatic number
• Defective coloring revisited
• Star coloring of graphs
• On a graph coloring problem arising from discrete tomography
• The NP-Completeness of Edge-Coloring
• Bounded vertex coloring of trees
• Hard tiling problems with simple tiles

This page was built for publication: Graph coloring with cardinality constraints on the neighborhoods