Wyniki wyszukiwania - BazTech

1

Facial rainbow edge-coloring of simple 3-connected plane graphs

Czap Julius

Opuscula Mathematica

|

2020

|

Vol. 40, no. 4

475--482

EN

A facial rainbow edge-coloring of a plane graph G is an edge-coloring such that any two edges receive distinct colors if they lie on a common facial path of G. The minimum number of colors used in such a coloring is denoted by erb(G). Trivially, erb(G) ≥ L(G) + 1 holds for every plane graph without cut-vertices, where L(G) denotes the length of a longest facial path in G. Jendrol’ in 2018 proved that every simple 3-connected plane graph admits a facial rainbow edge-coloring with at most L(G) + 2 colors, moreover, this bound is tight for L(G) = 3. He also proved that erb(G) = L(G) + 1 for L(G) ∉ {3,4, 5}. He posed the following conjecture: There is a simple 3-connected plane graph G with L(G) = 4 and erb(G) = L(G) + 2. In this note we answer the conjecture in the affirmative. Keywords: plane graph, facial path, edge-coloring.

2

Local Face Antimagic Evaluations and Coloring of Plane Graphs

Bong Novi, Bača Martin, Semaničová-Feňovčíková Andrea, Sugeng Kiki A., Wang Tao-Ming

Fundamenta Informaticae

|

2020

|

Vol. 174, nr 2

103--119

EN

We investigate a local face antimagic labeling of plane graphs, and we introduce a new graph characteristic, namely local face antimagic chromatic number of type (a, b, c). Then we determine the precise value of this parameter for wheels and ladders.

3

Zig-zag facial total-coloring of plane graphs

Czap J., Jendrol S., Voigt M.

Opuscula Mathematica

|

2018

|

Vol. 38, no. 6

819--827

EN

In this paper we introduce the concept of zig-zag facial total-coloring of plane graphs. We obtain lower and upper bounds for the minimum number of colors which is necessary for such a coloring. Moreover, we give several sharpness examples and formulate some open problems.

4

Minimal unavoidable sets of cycles in plane graphs

Madaras T., Tamasova M.

Opuscula Mathematica

|

2018

|

Vol. 38, no. 6

859--870

EN

A set S of cycles is minimal unavoidable in a graph family [formula] if each graph [formula] contains a cycle from S and, for each proper subset S' ⊂ S, there exists an infinite subfamily [formula] such that no graph from [formula] contains a cycle from S'. In this paper, we study minimal unavoidable sets of cycles in plane graphs of minimum degree at least 3 and present several graph constructions which forbid many cycle sets to be unavoidable. We also show the minimality of several small sets consisting of short cycles

5

Designing and Learning Substitutable Plane Graph Grammars

Eyraud R., Oates T., Janodet J.-C., Papadopoulos F.

Fundamenta Informaticae

|

2016

|

Vol. 146, nr 4

403--430

EN

Though graph grammars have been widely investigated for 40 years, few learning results exist for them. The main reasons come from complexity issues that are inherent when graphs, and a fortiori graph grammars, are considered. The picture is however different if one considers drawings of graphs, rather than the graphs themselves. For instance, it has recently been proved that the isomorphism and pattern searching problems could be solved in polynomial time for plane graphs, that is, planar embeddings of planar graphs. In this paper, we introduce the Plane Graph Grammars (PGG) and detail how they differ to usual graph grammar formalism’s while at the same time they share important properties with string context-free grammars. In particular, though exponential in the general case, we provide an appropriate restriction on languages that allows the parsing of a graph with a given PGG in polynomial time. We demonstrate that PGG are well-shaped for learning: we show how recent results on string grammars can be extended to PGG by providing a learning algorithm that identifies in the limit the class of substitutable plane graph languages. Our algorithm runs in polynomial time assuming the same restriction used for polynomial parsing, and the amount of data needed for convergence is comparable to the one required in the case of strings.