Projective, affine, and abelian colorings of cubic graphs

J 2009

Projective, affine, and abelian colorings of cubic graphs

KRÁĽ, Daniel; E MACAJOVA; O PANGRAC; A RASPAUD; JS SERENI et. al.

Základní údaje

Originální název

Projective, affine, and abelian colorings of cubic graphs

Autoři

KRÁĽ, Daniel; E MACAJOVA; O PANGRAC; A RASPAUD; JS SERENI a M SKOVIERA

Vydání

European Journal of Combinatorics, LONDON, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2009, 0195-6698

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.822

DOI

http://dx.doi.org/10.1016/j.ejc.2007.11.029

UT WoS

000260960100008

Změněno: 6. 11. 2020 10:15, Mgr. Darina Boukalová

Anotace

V originále

We develop an idea of a local 3-edge-coloring of a cubic graph, a generalization of the usual 3-edge-coloring. We allow for an unlimited number of colors but require that the colors of two edges meeting at a vertex always determine the same third color. Local 3-edge-colorings are described in terms of colorings by points of a partial Steiner triple system such that the colors meeting at each vertex form a triple of the system. An important place in our investigation is held by the two smallest non-trivial Steiner triple systems, the Fano plane PG(2, 2) and the affine plane AG(2, 3). For i = 4, 5, and 6 we identify certain configurations F-i and A(i) of i lines of the Fano plane and the affine plane, respectively, and prove a theorem saying that a cubic graph admits an F-i-coloring if and only if it admits an A(i)-coloring. Among consequences of this is the result of Holroyd and Skoviera [F. Holroyd, M. Skoviera, Colouring of cubic graphs by Steiner triple systems, J. Combin. Theory Set. B 91 (2004) 57-66] that the edges of every bridgeless cubic graph can be colored by using points and blocks of any non-trivial Steiner triple system S.

Citovat

KRÁĽ, Daniel; E MACAJOVA; O PANGRAC; A RASPAUD; JS SERENI a M SKOVIERA. Projective, affine, and abelian colorings of cubic graphs. European Journal of Combinatorics. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2009, roč. 30, č. 1, s. 53-69. ISSN 0195-6698. Dostupné z: https://dx.doi.org/10.1016/j.ejc.2007.11.029.

@article{1689697,
   author = {Kráľ, Daniel and Macajova, E and Pangrac, O and Raspaud, A and Sereni, JS and Skoviera, M},
   article_location = {LONDON},
   article_number = {1},
   doi = {http://dx.doi.org/10.1016/j.ejc.2007.11.029},
   language = {eng},
   issn = {0195-6698},
   journal = {European Journal of Combinatorics},
   title = {Projective, affine, and abelian colorings of cubic graphs},
   volume = {30},
   year = {2009}
}

TY  - JOUR
ID  - 1689697
AU  - Kráľ, Daniel - Macajova, E - Pangrac, O - Raspaud, A - Sereni, JS - Skoviera, M
PY  - 2009
TI  - Projective, affine, and abelian colorings of cubic graphs
JF  - European Journal of Combinatorics
VL  - 30
IS  - 1
SP  - 53-69
EP  - 53-69
PB  - ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
SN  - 01956698
N2  - We develop an idea of a local 3-edge-coloring of a cubic graph, a generalization of the usual 3-edge-coloring. We allow for an unlimited number of colors but require that the colors of two edges meeting at a vertex always determine the same third color. Local 3-edge-colorings are described in terms of colorings by points of a partial Steiner triple system such that the colors meeting at each vertex form a triple of the system. An important place in our investigation is held by the two smallest non-trivial Steiner triple systems, the Fano plane PG(2, 2) and the affine plane AG(2, 3). For i = 4, 5, and 6 we identify certain configurations F-i and A(i) of i lines of the Fano plane and the affine plane, respectively, and prove a theorem saying that a cubic graph admits an F-i-coloring if and only if it admits an A(i)-coloring. Among consequences of this is the result of Holroyd and Skoviera [F. Holroyd, M. Skoviera, Colouring of cubic graphs by Steiner triple systems, J. Combin. Theory Set. B 91 (2004) 57-66] that the edges of every bridgeless cubic graph can be colored by using points and blocks of any non-trivial Steiner triple system S.
ER  -

KRÁĽ, Daniel; E MACAJOVA; O PANGRAC; A RASPAUD; JS SERENI a M SKOVIERA. Projective, affine, and abelian colorings of cubic graphs. \textit{European Journal of Combinatorics}. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2009, roč.~30, č.~1, s.~53-69. ISSN~0195-6698. Dostupné z: https://dx.doi.org/10.1016/j.ejc.2007.11.029.

Přehled o publikaci