TAILIEUCHUNG - Báo cáo toán học: "On oriented arc-coloring of subcubic graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On oriented arc-coloring of subcubic graphs. | On oriented arc-coloring of subcubic graphs Alexandre Pinlou E-mail LaBRI Université Bordeaux 1 351 Cours de la Libération 33405 Talence Cedex France Submitted Jan 17 2006 Accepted Aug 2 2006 Published Aug 7 2006 Mathematics Subject Classification 05C15 Abstract A homomorphism from an oriented graph G to an oriented graph H is a mapping from the set of vertices of G to the set of vertices of H such that u v is an arc in H whenever u is an arc in G. The oriented chromatic index of an oriented graph G is the minimum number of vertices in an oriented graph H such that there exists a homomorphism from the line digraph LD G of G to H Recall that LD G is given by V LD G A G and a 2 A LD G whenever a u and b - . We prove that every oriented subcubic graph has oriented chromatic index at most 7 and construct a subcubic graph with oriented chromatic index 6. Keywords Graph coloring oriented graph coloring arc-coloring subcubic graphs. 1 Introduction We consider finite simple oriented graphs that is digraphs with no opposite arcs. For an oriented graph G we denote by V G its set of vertices and by A G its set of arcs. In 2 Courcelle introduced the notion of vertex-coloring of oriented graphs as follows an oriented k-vertex-coloring of an oriented graph G is a mapping from V G to a set of k colors such that i u v whenever u is an arc in G and ii u x whenever u and w are two arcs in G with v w . The oriented chromatic number of an oriented graph G denoted by ỵo G is defined as the smallest k such that G admits an oriented k-vertex-coloring. Let H and H be two oriented graphs. A homomorphism from H to H is a mapping from V H to V H0 that preserves the arcs u v 2 A H0 whenever u 2 A H . An oriented k-vertex-coloring of G can be equivalently defined as a homomorphism from THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R69 1 G to H where H is an oriented graph of order k. The existence of such a homomorphism from G to H is denoted by G H. The graph H .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.