Strong parity vertex coloring of plane graphs

Strong parity vertex coloring of plane graphs

Show other versions (1)

A strong parity vertex coloring of a 2-connected plane graph is a coloring of the vertices such that every face is incident with zero or an odd number of vertices of each color. We prove that every 2-connected loopless plane graph has a strong parity vertex coloring with 97 colors. Moreover the colo...

书目详细资料
Main Authors:	Tomas Kaiser, Ondrej Rucky, Matej Stehlik, Riste Skrekovski
格式:	文件
语言:	English
出版:	Discrete Mathematics & Theoretical Computer Science 2014-01-01
丛编:	Discrete Mathematics & Theoretical Computer Science
主题:	[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
在线阅读:	https://dmtcs.episciences.org/640/pdf

相似书籍

Strong parity vertex coloring of plane graphs
由: Tomas Kaiser, et al.
出版: (2014-03-01)

A bound on the number of perfect matchings in Klee-graphs
由: Marek Cygan, et al.
出版: (2013-01-01)

On the complexity of vertex-coloring edge-weightings
由: Andrzej Dudek, et al.
出版: (2011-11-01)

Long cycles in hypercubes with distant faulty vertices
由: Petr Gregor, et al.
出版: (2009-01-01)

Gray codes avoiding matchings
由: Darko Dimitrov, et al.
出版: (2009-01-01)

Graphs with many vertex-disjoint cycles
由: Dieter Rautenbach, et al.
出版: (2012-09-01)

On the complexity of the balanced vertex ordering problem
由: Jan Kára, et al.
出版: (2007-01-01)

An expected polynomial time algorithm for coloring 2-colorable 3-graphs
由: Yury Person, et al.
出版: (2011-05-01)

All totally symmetric colored graphs
由: Mariusz Grech, et al.
出版: (2013-03-01)

Irregular edge coloring of 2-regular graphs
由: Sylwia Cichacz, et al.
出版: (2011-02-01)

Immersion containment and connectivity in color-critical graphs
由: Faisal N. Abu-Khzam, et al.
出版: (2012-10-01)

On paths, trails and closed trails in edge-colored graphs
由: Laurent Gourvès, et al.
出版: (2012-09-01)

A note on compact and compact circular edge-colorings of graphs
由: Dariusz Dereniowski, et al.
出版: (2008-01-01)

Binary Labelings for Plane Quadrangulations and their Relatives
由: Stefan Felsner, et al.
出版: (2011-01-01)

Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
由: Gábor Bacsó, et al.
出版: (2009-01-01)

Some results on stable sets for k-colorable P₆-free graphs and generalizations
由: Raffaele Mosca
出版: (2012-08-01)

List edge and list total colorings of planar graphs without non-induced 7-cycles
由: Aijun Dong, et al.
出版: (2013-03-01)

On the tileability of polygons with colored dominoes
由: Chris Worman, et al.
出版: (2007-01-01)

Nonrepetitive colorings of lexicographic product of graphs
由: Balázs Keszegh, et al.
出版: (2014-10-01)

Parameterized Problems Related to Seidel's Switching
由: Eva Jelinkova, et al.
出版: (2011-05-01)

Detection number of bipartite graphs and cubic graphs
由: Frederic Havet, et al.
出版: (2014-12-01)

Acyclic chromatic index of fully subdivided graphs and Halin graphs
由: Manu Basavaraju
出版: (2012-10-01)

Probe split graphs
由: Van Bang Le, et al.
出版: (2007-01-01)

Generation of Cubic graphs
由: Gunnar Brinkmann, et al.
出版: (2011-07-01)

Leftmost derivations of propagating scattered context grammars: a new proof
由: Tomáš Masopust, et al.
出版: (2008-01-01)

On the metric dimension of Grassmann graphs
由: Robert F. Bailey, et al.
出版: (2012-01-01)

On economical set representations of graphs
由: Jing Kong, et al.
出版: (2009-01-01)

On hereditary Helly classes of graphs
由: Marina Groshaus, et al.
出版: (2008-01-01)

The determining number of Kneser graphs
由: José Cáceres, et al.
出版: (2013-01-01)

On 4-valent Frobenius circulant graphs
由: Sanming Zhou
出版: (2012-10-01)

The Erdős-Sós conjecture for geometric graphs
由: Luis Barba, et al.
出版: (2013-02-01)

Progress on the traceability conjecture for oriented graphs
由: Marietjie Frick, et al.
出版: (2008-01-01)

Complexity results on graphs with few cliques
由: Bill Rosgen, et al.
出版: (2007-01-01)

On Compact Encoding of Pagenumber $k$ Graphs
由: Cyril Gavoille, et al.
出版: (2008-01-01)

Extremal K_(s,t)-free bipartite graphs
由: Camino Balbuena, et al.
出版: (2008-01-01)

On the chromatic number of some flip graphs
由: Ruy Fabila-Monroy, et al.
出版: (2009-01-01)

Upper k-tuple domination in graphs
由: Gerard Jennhwa Chang, et al.
出版: (2012-12-01)

Cycle transversals in bounded degree graphs
由: Marina Groshaus, et al.
出版: (2011-03-01)

The resolving number of a graph Delia
由: Delia Garijo, et al.
出版: (2013-12-01)

Total domination in K₅- and K₆-covered graphs
由: Odile Favaron, et al.
出版: (2008-01-01)